As is known to those of skill in the art, a modulo operation, commonly written as a mod d, returns the remainder after the division of a first number (the dividend, a) by a second number (the divisor, d). The remainder may also be referred to as the modulo value.
There are several methods which can be used to implement a modulo operation in hardware logic (e.g. integrated circuit). Such hardware logic may form part of a processor such as a CPU (central processing unit) or GPU (graphics processing unit). One example method calculates the modulo value as a natural by-product of an iterative division implementation (e.g. an iterative division which calculates a/d). In particular, where the divisor, d, is a constant a divider can be optimized to only divide by the constant d and output the modulo value of a as the output.
Other example methods use other division methods, which don't produce a modulo value naturally, in combination with multiplication and subtraction to calculate the modulo value using the identity of equation (1):
                              a          ⁢                                          ⁢          mod          ⁢                                          ⁢          d                =                  a          -                      d            *                          ⌊                              a                d                            ⌋                                                          (        1        )            
In other examples, where the divisor d is a multiple of a power of 2 (i.e. d=2k d0) the problem of determining the modulo value may be reduced to determining the modulo value of d0 by outputting the least significant k bits of the input. This means that that only odd d0 need to be considered. Therefore x [n−1:0] mod d can be broken down into x [n−1:k] mod d0 concatenated with x [k−1:0]. For example x mod 6 (k=1) can be broken down as shown in equation (2) wherein “&” indicates a concatenation of bit strings.x[n−1:0] mod 6=(x[n−1:1] mod 3) & x[0]  (2)
The embodiments described below are provided by way of example only and are not limiting of implementations which solve any or all of the disadvantages of known methods of generating a hardware design for implementing a modulo operation.